package main.Q901_1000;

import java.util.Arrays;
import java.util.Comparator;

public class Q971_980 {
    public static void main(String[] args) {
        System.out.println("Question971：");
        System.out.println("Question972：");
        System.out.println("Question973：最接近原点的K个点");
        System.out.println("Question974：");
        System.out.println("Question975：");
        System.out.println("Question976：三角形的最大周长");
        System.out.println("Question977：有序数组的平方");
        System.out.println("Question978：");
        System.out.println("Question979：");
        System.out.println("Question980：不同路径 III");
    }
}

class Question973 {
    public int[][] kClosest(int[][] points, int k) {
        int[][] result = new int[k][];
        double[][] distance = new double[points.length][2];
        for (int i = 0; i < points.length; i++) {
            distance[i][1] = i;
            int[] curPoint = points[i];
            distance[i][0] = Math.sqrt((Math.pow(curPoint[0], 2) + Math.pow(curPoint[1], 2)));
        }
        Arrays.sort(distance, new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                if (o1[0] != o2[0]) return o1[0] - o2[0] > 0 ? 1 : -1;
                else return o1[1] - o2[1] > 0 ? 1 : -1;
            }
        });
        for (int i = 0; i < k; i++) {
            int index = (int) distance[i][1];
            result[i] = points[index];
        }
        return result;
    }
}

class Question976 {
    public int largestPerimeter(int[] nums) {
        int C = 0, length = nums.length, i = length - 1, j = length - 2, k = length - 3;
        Arrays.sort(nums);
        for (; k >= 0; ) {
            if (nums[i] < nums[j] + nums[k]) {//满足
                C = nums[i] + nums[j] + nums[k];
                break;
            } else if (nums[i] >= nums[j] + nums[k]) {//不能满足
                i--;
                j--;
                k--;
            }
        }
        return C;
    }
}

class Question977 {
    public static int[] sortedSquares(int[] nums) {//双指针
        int length = nums.length, left = 0, right = length - 1;
        int[] result = new int[length];
        int powLeft = 0, powRight = 0, index = length - 1;
        while (index >= 0) {
            powLeft = nums[left] * nums[left];
            powRight = nums[right] * nums[right];
            if (powLeft >= powRight) {
                result[index] = powLeft;
                left++;
                index--;
            } else {
                result[index] = powRight;
                right--;
                index--;
            }
        }
        return result;
    }
}

class Question980 {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int uniquePathsIII(int[][] grid) {
        int r = grid.length, c = grid[0].length;
        int si = 0, sj = 0, n = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 0) {
                    n++;
                } else if (grid[i][j] == 1) {
                    n++;
                    si = i;
                    sj = j;
                }
            }
        }
        return process(grid, si, sj, n);
    }

    public int process(int[][] grid, int i, int j, int n) {
        if (grid[i][j] == 2) {
            return n == 0 ? 1 : 0;
        }
        int r = grid.length, c = grid[0].length;
        int t = grid[i][j];
        grid[i][j] = -1;
        int result = 0;
        for (int[] dir : dirs) {
            int ni = i + dir[0], nj = j + dir[1];
            if (ni >= 0 && ni < r && nj >= 0 && nj < c && (grid[ni][nj] == 0 || grid[ni][nj] == 2)) {
                result += process(grid, ni, nj, n - 1);
            }
        }
        grid[i][j] = t;
        return result;
    }
}